package com.yehui.algorithm.sword;

/**
 * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
 * Created by XuChunH on 2016/9/16.
 */
public class Power {
    public double power(double base, int exponent) {
        double result = 1.0;
        if(exponent == 0){
            return result;
        }
        int num = Math.abs(exponent);
        for (int i = 0; i < num; i++) {
            result *= base;
        }
        if(exponent < 0){
            result = 1 / result;
        }
        return result;
    }

    /**
     * n为偶数，a^n=a^n/2*a^n/2;n为奇数，a^n=（a^（n-1）/2）*（a^（n-1/2））*a 时间复杂度O（logn）
     * @param base
     * @param exponent
     * @return
     */
    public double power2(double base, int exponent){
        double result = 1.0;
        double temp = base;
        if(exponent == 0){
            return result;
        }
        if(base == 0 && exponent < 0){
            throw new RuntimeException("base is zero");
        }
        int num = Math.abs(exponent);
        while(num != 0){
            if((num & 1) == 1){
                result *= temp;
            }
            temp *= temp;
            num = num >> 1;
        }
        return exponent > 0 ? result : 1 / result;
    }
}
